package arithmetic.climbstairs;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangzg
 * @date 2022/10/8
 * 爬楼梯算法
 * 1、先根据描述提炼出数学公式。
 * f(n)=f(n-1)+f(n-2)
 * 2、跟根据数学公式用代码实现
 */
public class Test {

    private static Map<Integer,Integer> map=new HashMap<Integer,Integer>();

    public static void main(String[] args) {
        System.out.println(calc(45));
        System.out.println(calc1(45));
    }

    /**
     * 递归
     * @param n
     * @return
     */
    public static int calc(int n){
        if (n==1) return 1;
        if (n==2) return 2;
        if(map.get(n)!=null){
            return map.get(n);
        }else {
            int result=calc(n-1)+calc(n-2);
            map.put(n,result);
            return result;
        }
    }

    /**
     * 循环
     */
    public static int calc1(int n){
        if (n==1) return 1;
        if (n==2) return 2;
        int result=0;
        int pre=2;
        int prePre=1;
        for (int i=3;i<=n;i++){
            result=pre+prePre;
            prePre=pre;
            pre=result;
        }
        return result;
    }
}
